Bingo, Computer Graphics & Game Developer

Screen Space Fog of War

战争迷雾本身有着非常多的实现方案，类似Dota这样的MOBA游戏早在WC3中就有迷雾的效果实现。这里介绍一个基于屏幕空间战争迷雾的实现效果。

1563212000634

WC3

基于屏幕空间的战争迷雾，其核心是一张2D的ShadowMap，之后只需要在全屏Pass下，利用Depth+ClipSpacePosition来重建世界坐标，再从世界坐标转换到2D阴影贴图的局部坐标系下，即可得到当前像素的阴影值。

float depth = DepthTexture.Sample(positionNDC);
float3 positionWS = float4(float3(positionNDC, depth) * 2.0 - 1.0f, 1.0f);
positionWS = mul(_inverseVP, positionWS);
positionWS.xyz /= positionWS.w;

DepthAndPositionWS

左图为Depth, 右图为重建出的WorldSpace Position。

因此基于屏幕空间的战争迷雾，最核心的就是计算得到的2D阴影贴图，以下列举的不同方案只是在计算这张阴影贴图的过程有所不同。

Grid

Introduction

1564411522311

网格方案在WC3时代就已经被广泛应用，将地图预计算为一张地图障碍物贴图，CPU根据玩家位置实时填充数据，以计算视野阴影贴图。最后转为GPU可读的RT作为2D Shadow。由于CPU填充能力较低，一般最后会辅以Blur来弥补画面缺陷。

Grid-3

左图为预计算的地图障碍物贴图，中间为当前帧可视范围。这里对象移动过的范围将会被标记为已探索，一般实际游戏会对这块区域做提亮操作，如图中白色部分表示为已知探索范围。

核心的CPU填充算法非常直观，本质就是借助队列实现的四邻域填充算法

queue.Enqueue(rootPixel);
while(queue.Count > 0) {
	current = queue.Dequeue();

	// if rootPixel could see current pixel
	if(RayCast(current, rootPixel)) 
		SetVisible(root);

	// spread the visible area around root position in four direction
	EnqueueAtPosition(root.x - 1, root.y, rootPixels, radius);
	EnqueueAtPosition(root.x, root.y - 1, rootPixels, radius);
	EnqueueAtPosition(root.x + 1, root.y, rootPixels, radius);
	EnqueueAtPosition(root.x, root.y + 1, rootPixels, radius);
}

由于CPU在填充过程中需要等待，因此将数据更新另开线程，则阴影贴图的更新可以延迟于玩家移动，不影响主线程整体运行表现。

Grid-4

为了弥补多线程填充完成带来的突变感，存下当前迷雾帧以及上一帧的数据(Texture中R和B通道)，在渲染时对其进行插值过渡，以避免突兀。

在WC3中，移动到一定距离才会触发迷雾的更新，和上述思路基本类似

FOWGrid0

网格方案较为流行也容易实现，但由于CPU填充能力有限，即便是能做到仅对脏区域局部更新，CPU仍然对高分辨率的需求无法得到较好的满足，且最后一般都需要提供较为高昂的Blur来模糊分辨率带来的界限。不过由于迷雾的特性，低分辨率有时反倒在边缘上能带来更好的过渡感。

Reference

游戏中的战争迷雾

【Unity】FOV战争迷雾

unity下一种基于渲染可见区域的战争迷雾

Signed Distance Field Shadow

Introduction

FinalResult-1

SDF方案对CPU最为友好，几乎所有计算都可以在GPU中完成。若为静态场景可预bake场景成一张障碍物贴图，动态场景可使用正交投影相机在上方正交拍摄Depth再转换得到。之后使用SDF生成算法对这张障碍物贴图计算Min Signed Distance。最后对这张SDF进行RayMarching来得到一张2D阴影贴图。

MapDataAndSDF

从左至右依次为场景Map的障碍物信息，计算得到的SDF贴图，以及最终的2D阴影贴图。

本文选用JFA算法(Reference[1]Reference^{[1]})来实时更新SDF贴图。其支持GPU并行，且复杂度仅为O(Nlogn)。要求是Texture的分辨率需要为2的幂次方。

JFA-1

链接为作者描述JFA的Phd论文，也可以查看Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform，但上面这篇在错误分析和变种应用上讲解的更为详尽。

SDF生成算法有较多种，可以参考[2]^{[2]}中第五章中提供的几种经典算法来生成SDF贴图

JFA的具体思路就是，将复杂的待计算的格点p到3D表面或者2D形状边缘的距离，转化多Pass下，每个Pass中p找到八邻域3D/2D坐标于Seed的距离。其选择的八邻域到p的距离Step，将会不断除2直至为1(logN/2, logN/4, … 16, 8, 4, 2, 1)后得到最终的SDF Texture。

float power = Math.Log2(textureWidth);
for(int i = 0; i <= power; i++) {
	int index0 = i % 2;
	int index1 = (i + 1) % 2;
	
	mat.SetFloat("_Power", power);
	mat.SetFloat("_Level", i);
	mat.SetTexture("_SDFTexture", pingpong[index0]);

	Blit(mat, pingpong[index1]);
}

float stepwidth = _Power - _Level + 1;

for (int y = -1; y <= 1; ++y) {
	for (int x = -1; x <= 1; ++x) {
		// Sample semi-finished sdf texture
		float2 uv = texCoord + float2(x, y) * _TexelSize * stepwidth;
		float4 value = Sample(_SDFTexture, uv);
		float2 seedCoord  = value.zw;
 
		float distance = length(texCoord - seedCoord);
		if ((seedCoord.x != 0.0 || seedCoord.y != 0.0) && distance < minDistance) {
			minDistance = distance;
			minCoord    = seedCoord;
        }
    }
}

JFA本身是存在一定error的，但作者在文章中对不同场景提出了几个算法上的变种(JFA2, 1+JFA…)用于减少Error。上述Phd论文中还分享了在Voronoi Diagram，Delaunay Triangulation, Direct Shadow等应用的原理

计算2D Shadow中的Sphere RayMarching本身很好理解，将SDF图中采样的值，也就是到边界的最近距离作为步进的最长距离(步进更大的距离将可能与已有边界碰撞)。

float drawShadow(float2 uv, float2 lightPos)
{
    float2 direction = normalize(lightPos - uv);
    float2 p = uv;
    float distanceToLight = length(uv - lightPos);
    float distance = 0.0f;

    for(int i = 0; i < 32; i++) {
        float s = Sample(_SDFTexture, p);

        if(s <= 0.00001) return 0.0;
        if(distance > distanceToLight) return 1.0;

        distance += max(s * _StepScale, _StepMinValue);
        p = uv + direction * distance;
    }

    return 0.0;
}

SDF本身是可以直接计算出半影的，但在边界上存在较为严重的BandingArtifact，各类文献报告中均有对此进行改善缓解，一般会选用混合方案来避免这样的问题。其中也有改进后的ConeTracing方法，在UE4以及Reference[2]Reference^{[2]}中有过提及。

SDF2

左图为SDF直接计算得到的半影，右图则为在边界上RayMarching带来的精度不够导致的BandingArtifact现象

演示中为了避免BandingArtifact，并没有直接算出半影而是算出二值图最后配合Blur，并按距离增大Blur半径来模拟半影的效果。

FOWSDF0

Reference

Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform

Signed Distance Fields in Real-Time Rendering

Chapter 30. Real-Time Simulation and Rendering of 3D Fluids

Jump Flood Algorithm: Points

Jump Flood Algorithm: Shapes

2d signed distance functions

Mesh Projetion

Introduction

SFSS-0

2D阴影由于其特殊性，可以由CPU直接计算出一个变形后的Mesh作为平面的阴影区域。

SFSS-2-1567850455727

这里需要对障碍物进行边缘编辑，以调整出适应形状的阴影区域

对场景中所有变形后的Mesh，多次的渲染到一张RT上，即可得到所需的2D Shadow Map(本方法在Demo中并未涵盖，可参考Asset Store的SFSS插件)

若是场景中物体较多，则计算阴影区域的CPU压力将会较大，且即便为静态场景可能也需要多次的DrawMesh才能得到最后的2D ShadowMap。但其优势是在Shader中较前两者，可以较好的控制半影区域的绘制，以得到高质量的阴影结果。

SFSS-4-1567850431805

Reference

Unity Asset Store: SF Soft Shadow 2D

Summary

由于实现战争迷雾的方案较多，这里仅提供一个Unity上的基于屏幕空间战争迷雾的提供了上述Grid和SDF方案实现的项目Fog of War以供参考(Mesh Projetion的方案可以直接使用Unity SFSS的插件)

Demo中SDF可使用较高分辨率来完成实时预览一般给定128x128或者256x256皆可(过高分辨率需要更多次的Blur来带来半影的效果)。

而CPU的填充版本则由于C填充性能有限，因此建议给定64 x 64或32 x 32获得更平滑的效果。